package sort;

/**
 * 这是递归版本的插入排序
 */
public class 插入排序 {
    public static void main(String[] args) {
        //1.拆分为对前N-1个排序，最后一个元素去前面找位置
        int[] array = new int[]{3, 4, 5, 8, 1, 4, 23, 51, 12, 14};
        InsertSort(array, array.length - 1);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

    /**
     * 函数的功能就是对多个元素作插入排序
     *
     * @param array
     * @param index
     */
    static void InsertSort(int[] array, int index) {
        if (index == 0) {
            return;
        }
        InsertSort(array, index - 1);
        //去前面找位置
        int x = array[index];
        int k = index - 1;
        while (k > -1 && x < array[k]) {
            array[k + 1] = array[k];
            k--;
        }
        array[k + 1] = x;

    }
}
